package com.tgy.leetcode;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Author: tgy
 * @Date: 12/5/20 11:22 AM
 *
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 *
 * 后序反序列化二叉树从后往前前推，内部先right，后left
 */
public class _297_二叉树的序列化与反序列化_后序 {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

        StringBuilder sb = new StringBuilder("[");

        postorderTraversal(root,sb);

        if (sb.charAt(sb.length() - 1) == ',') {

            sb.deleteCharAt(sb.length() - 1);
        }

        sb.append("]");

        return sb.toString();
    }

    private void postorderTraversal(TreeNode root,StringBuilder sb) {

        if (root == null) {

            sb.append("null,");
            return;
        }

        postorderTraversal(root.left,sb);
        postorderTraversal(root.right,sb);
        sb.append(root.val).append(",");

    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

        if (data == null || !data.startsWith("[") || !data.endsWith("]")) {

            return null;
        }

        data = data.substring(1,data.length() - 1);

        if (data.length() == 0) {

            return null;
        }

        List<String> nodeVals = Arrays.stream(data.split(",")).collect(Collectors.toList());

        return general(nodeVals);
    }

    private TreeNode general(List<String> nodeVals) {

        String val;
        if (nodeVals.isEmpty() || (val = nodeVals.remove(nodeVals.size() -1)).equals("null")) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.right = general(nodeVals);
        root.left = general(nodeVals);

        return root;
    }
}
